Chapter 15 Exercise Answers

Change-Making Problem

We consider the change-making problem with available coin denominations \(\{1,3,5\}\).

Let \(dp[x]\) denote the minimum number of coins needed to make amount \(x\).

The recurrence relation is:

[ dp[0] = 0, dp[x] = 1 + (dp[x-1],, dp[x-3],, dp[x-5]) x , ]

ignoring any term with a negative index.

---

1. Recursive algorithm

# coins = {1, 3, 5} 
memo = {0: 0}          # base case: 0 coins to make 0
INF  = float("inf")

def MinCoinsTD(x):
    if x < 0: 
        return INF
    if x in memo: 
        return memo[x]

    # try all options; for this set it's x-1, x-3, x-5
    best_sub = min(MinCoinsTD(x-1), MinCoinsTD(x-3), MinCoinsTD(x-5))

    if best_sub == INF:
        memo[x] = INF          # still impossible
    else:
        memo[x] = 1 + best_sub # use one coin + best remainder

    return memo[x]

---

2. Recursion tree for \(x=7\)

(Students to draw manually.)

---

3. Recursive algorithm with memoization

(Already included above with memo dictionary.)

---

4. Saved recursive calls

For $x=7$, memoization prevents recomputation of overlapping subproblems.

---

5. Memo contents after computing $x=7$

memo = {0:0, 1:1, 2:2, 3:1, 4:2, 5:1, 6:2, 7:3}

---

6. Iterative bottom-up algorithm

def MinCoinsBU(n):
    dp = [float("inf")] * (n+1)
    dp[0] = 0

    for x in range(1, n+1):
        if x - 1 >= 0:
            dp[x] = min(dp[x], 1 + dp[x - 1])
        if x - 3 >= 0:
            dp[x] = min(dp[x], 1 + dp[x - 3])
        if x - 5 >= 0:
            dp[x] = min(dp[x], 1 + dp[x - 5])
    return dp[n]

```